When a record is created, it stays in a certain space on the disk. We seldom change its location, because changing the physical location for it is time-consuming (If you learned Operating System, the Disk is the lowest layer of your memory, which means it costs you a lot to lift it from the bottom)

Free-space map: A data structure (array) used to save space

Every block is assigned a value that shows the free space remaining in one block. Free space is space not occupied by data, $1-\text{block occupancy }$

2 means 2/8 of the space is free.

To store a new record, go to the array and find a suitable space. If it doesn't exist, assign it a new block. This approach is faster than a direct traversal lookup, but still not fast enough

Establishing a Two-Level Free Map: For example, where each element represents the maximum free space within 100 entries of the first-level free-space map.

In an exceptionally large relational graph, the first search time is reduced to 1/100, and the second search range is 100.

The cost of reducing search expenses is an increased cost of establishing the two-level free map. As a result, the establishment of the two-level free map is periodically written (rather than immediately updated), leading to potential outdated errors in the two-level free map.

Efficient handling of search keys (which can be any attribute or set of attributes) is achieved by organizing them in a linked list in sequential order (to minimize the number of block accesses in sequential file processing).

The benefit of sequential ordering is the ability to perform binary search (O(log N)).

Insert Operation:

1. Locate the record before the point of insertion.

2. Placement:
   1. If the block containing this record has space for at least one free record, insert this new record.
   2. Otherwise, insert the new record into an overflow block.

   

3. Adjust the connections of pointers.

Drawback: While initially fast due to physically adjacent blocks and sequentially ordered records, the efficiency of sequential processing decreases as the number of overflow blocks increases. The similarity between search keys and physical blocks diminishes, necessitating a file reorganization based on the existing order, which comes with a high cost.

In a single block, more than one relation's records are stored.

Calculating the relationship between the "department" and "instructor" relations:

sqlCopy code
SELECT dept_name, building, budget, ID, name, salary
FROM department NATURAL JOIN instructor

For each tuple in the "department" relation, the system must find instructor tuples with the same dept_name value.

In the worst case, each instructor record is stored in a different block → every time a required record is sought, a block read operation must be executed.

Multitable Clustering Definition:

All relation tuples $a_i$ pertaining to a specific A_B cluster are output near the $b_1$ corresponding to A_B. We say that relations A and B are clustered on the A_B key.

Cluster Key:

An attribute that defines which records are stored together, such as dept_name in the example.

Advantages: Accelerates specific join queries.

Disadvantages: Other operations may become slower.

In a table (relation), records (tuples) can be divided into smaller relations. This kind of table partitioning is often based on the values of an attribute.

For example, partitioning the "transaction" relation by year:

sqlCopy code
SELECT *
FROM transaction
WHERE year = 2019

After partitioning, only the transaction_2019 relation will be accessed.

Advantages:

1. Reducing the size of the table (relation) can decrease the time cost of operations, such as finding free space.

2. Different partitioned relations can be stored on different disks, based on access frequency.

The data in a database primarily resides on disks.

→ Accessing data on disks is slower than accessing data in memory.

→ Aim to minimize the number of blocks transferred between disk and memory.

→ Reduce the number of disk access times.

→ Keep as many blocks as possible in main memory.

→ Maximize the probability that the required blocks are already in main memory ← Keeping all blocks in main memory is impossible.

Buffer: An area in main memory used to store copies of disk blocks. The Buffer Manager is the system that allocates buffer space.

Double buffering can be used to read continuous stream of blocks Use of two buffers, A and B, for reading from disk (More than 2 buffers can be used)

Buffer Manager

When a disk block needs to be accessed (pseudocode):

if (block in buffer){
    return block address to caller
}
else{
    select a buffer that has been changed and write it back to the disk
    then replace its position with the target block
    return block address to caller
}

Buffer Replacement Strategies (Evicted):

1. Least Recently Used (LRU)

2. First in First Out (FIFO)

3. Most Recently Used (MRU)

• Pinned Block被钉住的块

  When a block is read from the buffer, if it is moved out by another process or is being written out while being removed from the buffer, problems may arise.

  Pin: A pinned block will not be moved out under any circumstances.

  Unpin: Used to release the pin after the read operation is completed.

• Shared and exclusive locks on buffer 共享排他锁

  When adding or removing tuples, no other processes should perform read operations.

  • Only one process can obtain an exclusive lock at a time.
    • When a process holds an exclusive lock, other processes cannot execute shared locks on the same block.
    • Exclusive locks can only be granted to processes one at a time.

  • A block with a shared lock cannot be held simultaneously with an exclusive lock.
    • If a process applies for an exclusive lock while holding a shared lock, it will not be immediately granted but will be in a waiting state.

  • Multiple processes can be concurrently given shared locks.
    • If a process applies for a shared lock on a block, and no other processes hold an exclusive lock on that block, then the shared lock can be granted.
    • Otherwise, the shared lock can be granted only after the exclusive lock is released.

• Buffer-Replacement Policies 替换策略

  A database system can predict future access patterns more accurately than an operating system.

  By examining each step required to perform user-requested operations, the database system can anticipate in advance which blocks will be needed.

• Toss-immediate strategy 立即丢弃策略

  Once the last tuple in a block of a relation file has been processed, the buffer manager should be instructed to free up the space occupied by this block.

  Perform a natural join operation and output all attributes.

  SELECT * FROM instructor NATURAL JOIN department;
  

  Pseudocode:

  for each tuple i of instructor do
  		for each tuple d of department do
  				if i[dept name]= d[dept name]
  				then begin
  						let x be a tuple defined as follows:
  						x[ID]:= i[ID]
  						x[dept name]:= i[dept name]
  						x[name]:= i[name]
  						x[salary]:= i[salary]
  						x[building]:= d[building]
  						x[budget]:= d[budget]
  						include tuple x as part of result of instructor ⋈ department
  				end
  		end
  end
  

  Once a block consisting of several elements in the instructor is processed, this block no longer needs to be stored in the main memory.

• Most recently used (MRU) 最近最经常使用策略

  Consider the department in the example above. When the for loop is processing a $department_i$, it is pinned.

  Once the for loop completes processing a $department_i$, this tuple will not appear in the subsequent for loops, so it is marked as Most Recently Used (MRU). It can be removed after unpinning.

• Column-Oriented Storage列式存储

  • Column-Oriented Storage

    Store each attribute of the relation separately.

    

    Advantages:

    • Reduces I/O if only a few attributes are accessed.
    • Improves CPU cache performance.
    • Enhances compression performance.
    • Modern CPU architectures with vector processing allow CPU operations to be applied in parallel to multiple elements of an array (e.g., comparing an attribute to a constant).

    Disadvantages:

    • Cost of reconstructing tuples from columnar representation.
    • Cost of tuple deletion and updates.
    • Cost of decompression.

    Columnar representation is often more effective in decision support than row-oriented representation.

    Some databases support both representations, known as row/column mixed storage.